Yuri Villanueva, Henry Herzfeld, Michael Keller¶
Introduction¶
We chose to explore how spam filtering would be solved by classifiers from each of the five tribes. The data set that we used was taken from the Apache SpamAssassin website. [2] It has over 2,500 labeled examples each of spam and non-spam (henceforth called ham). To build our classifiers, we used the free software machine-learning library scikit-learn (also known as sklearn). [3] The tools in sklearn made it convenient to transform the raw, labeled e-mail examples into word-frequency vectors and other formats for input. Scikit-learn even has useful tools for dividing the data set into training and test sets, and also for cross-validation.
The next sections discuss the details of each of our classifiers.
Preparing the dataset¶
The SpamAssassin datatset has the raw text of each e-mail message, including the header. Some of the messages are in html format, complete with markup tags. These headers and tags were removed so that scikit could use the data. The resulting plain body text messages are then tokenized and stemmed. That is, our notebook removes small words like the, is, of, etc., when compiling a list of unique tokens. It also does stemming so that words like jumps, jumped, and jumping are reduced to the single stem jump.
Collecting all of the stems from all of the e-mail messages in the dataset resulted in over 24,000 unique words that we could use as attibutes. Yet another transformation was needed before we could use sklearn's built-in classifiers. From each e-mail message, we created a 24,000+-long vector of relative word frequencies. The dataset, as a whole, was thus represented as a sparse matrix.
After processing and transforming the dataset, we used an 80%-20% split for training and validation. This comes out to roughly 2,000 spam and 2,000 ham messages for training, and 500 each for testing.
The Symbolists¶
The first tribe discussed by Domingos are the Symbolists. Their master algorithm is inverse deduction, which is computationally expensive and hard to scale to large data sets. [1] Domingos writes, "For these, the symbolist algorithm of choice is decision tree induction. Decision trees can be viewed as an answer to the question of what to do if rules of more than one concept match an instance."
Sklearn has a decision tree classifier built in. Configured with a depth of only three levels down from the root, a decision tree built from our training data already has an 84% accuracy score on the validation set, correctly clasifying 383 of 527 spam, and 477 of 504 ham messages:
# Decision tree, max_depth = 3
dt3 = tree.DecisionTreeClassifier(max_depth=3)
print(*fit_evaluate_model(X_train, X_test, y_train, y_test, dt3))
plot_tree(dt3)
If the measure of statistical dispersion is left unspecified, sklearn's built-in decision tree classifier uses the Gini coefficient, instead of information entropy. The resulting root node makes the split at attribute X[3653], which corresponds to the word click. It's entirely believable that spam messages would contain this word much more often than normal.
With max_depth = 10, the accuracy jumps up to 94%:
# Decision tree, max_depth=10
dt10 = tree.DecisionTreeClassifier(max_depth=10)
print(*fit_evaluate_model(X_train, X_test, y_train, y_test, dt10))
plot_tree(dt10)
If we leave max_depth unspecified and, instead, accept whatever sklearn has for the default maximum tree depth, the accuracy goes up yet again--96.7% on the validation set. But something strange happens to the shape of the decision tree:
# Decision tree, max_depth unspecified
dt = tree.DecisionTreeClassifier()
print(*fit_evaluate_model(X_train, X_test, y_train, y_test, dt))
plot_tree(dt)
Look at the long tail on the left! It goes 43 levels down from the root. At this point one has to wonder if it's memorizing how to classify specific instances in the training set. It sure does look like overfitting. Here's how the accuracy changes with maximum tree depth:
# Decision tree, accuracy vs. depth
for i in range(43):
dt = tree.DecisionTreeClassifier(max_depth = i+1)
result = fit_evaluate_model(X_train, X_test, y_train, y_test, dt)
print(i+1,result[2])
This is more evidence of overfitting. It looks like the performance on the test set no longer improves past a maximum depth of 15 or so.
Connectionists¶
For the connectionist approach, we used the simplest type of neural network, a multi-layer perceptron, or MLP. By default, the MLP from scikit-learn has an input layer, a single hidden layer with 100 hidden nodes, and an output layer. For each hidden node, it uses an activation function of Rectified Linear Unit, or ReLU. For an optimzer, it uses Adam, an adaptive version of stochastic gardient descent. The minibatch size is 200 by default. The learning rate is a constant value of 0.001. Below we can see the results of these default parameters:
# Connectionists
nn = MLPClassifier()
print(*fit_evaluate_model(X_train, X_test, y_train, y_test, nn))
As we can see, a classification accuracy of 99% shows that the MLP with default parameters in scikit-learn can perform spam detection quite well. However, for the purposes of experimentation, we will change some of these parameters to see how they effect the classification accuracy. We can see the new runs of the network with these parameters below:
nn = MLPClassifier(hidden_layer_sizes=(1,))
print(*fit_evaluate_model(X_train, X_test, y_train, y_test, nn))
nn = MLPClassifier(hidden_layer_sizes=(5,))
print(*fit_evaluate_model(X_train, X_test, y_train, y_test, nn))
nn = MLPClassifier(hidden_layer_sizes=(25,))
print(*fit_evaluate_model(X_train, X_test, y_train, y_test, nn))
nn = MLPClassifier(hidden_layer_sizes=(50,))
print(*fit_evaluate_model(X_train, X_test, y_train, y_test, nn))
nn = MLPClassifier(hidden_layer_sizes=(200,))
print(*fit_evaluate_model(X_train, X_test, y_train, y_test, nn))
nn = MLPClassifier(hidden_layer_sizes=(400,))
print(*fit_evaluate_model(X_train, X_test, y_train, y_test, nn))
As we can see, changing the number of nodes in the hidden layer only causes minor fluctuations in the performance of the MLP classifier. We note that an MLP with 5 nodes in the hidden layer produces the same performance as the default classifier with 100 hidden nodes. So, the next experiments will use 5 hidden nodes to significantly decrease runtime. Next, we use the other 3 activation functions that come with scikit-learn's MLP:
nn = MLPClassifier(hidden_layer_sizes=(5,), activation='identity')
print(*fit_evaluate_model(X_train, X_test, y_train, y_test, nn))
nn = MLPClassifier(hidden_layer_sizes=(5,), activation='logistic')
print(*fit_evaluate_model(X_train, X_test, y_train, y_test, nn))
nn = MLPClassifier(hidden_layer_sizes=(5,), activation='tanh')
print(*fit_evaluate_model(X_train, X_test, y_train, y_test, nn))
From these results we see that there is no justifiable difference in performance when changing the activation function from the default choice, ReLU. Next we will play with the batch size:
nn = MLPClassifier(hidden_layer_sizes=(5,), batch_size=1)
print(*fit_evaluate_model(X_train, X_test, y_train, y_test, nn))
nn = MLPClassifier(hidden_layer_sizes=(5,), batch_size=2)
print(*fit_evaluate_model(X_train, X_test, y_train, y_test, nn))
nn = MLPClassifier(hidden_layer_sizes=(5,), batch_size=4)
print(*fit_evaluate_model(X_train, X_test, y_train, y_test, nn))
nn = MLPClassifier(hidden_layer_sizes=(5,), batch_size=8)
print(*fit_evaluate_model(X_train, X_test, y_train, y_test, nn))
nn = MLPClassifier(hidden_layer_sizes=(5,), batch_size=16)
print(*fit_evaluate_model(X_train, X_test, y_train, y_test, nn))
nn = MLPClassifier(hidden_layer_sizes=(5,), batch_size=32)
print(*fit_evaluate_model(X_train, X_test, y_train, y_test, nn))
nn = MLPClassifier(hidden_layer_sizes=(5,), batch_size=64)
print(*fit_evaluate_model(X_train, X_test, y_train, y_test, nn))
nn = MLPClassifier(hidden_layer_sizes=(5,), batch_size=128)
print(*fit_evaluate_model(X_train, X_test, y_train, y_test, nn))
nn = MLPClassifier(hidden_layer_sizes=(5,), batch_size=256)
print(*fit_evaluate_model(X_train, X_test, y_train, y_test, nn))
nn = MLPClassifier(hidden_layer_sizes=(5,), batch_size=512)
print(*fit_evaluate_model(X_train, X_test, y_train, y_test, nn))
nn = MLPClassifier(hidden_layer_sizes=(5,), batch_size=1024)
print(*fit_evaluate_model(X_train, X_test, y_train, y_test, nn))
nn = MLPClassifier(hidden_layer_sizes=(5,), batch_size=2048)
print(*fit_evaluate_model(X_train, X_test, y_train, y_test, nn))
There is a slight accuracy increase for lower batch sizes. As batch sizes increase, running times exponentially increase. So, for future runs, we will use a batch size of 128, the highest batch size that observed a slight performance increase. Finally, we will play with the learning rate for the Adam optimizer below:
nn = MLPClassifier(hidden_layer_sizes=(5,), batch_size=128, learning_rate_init=0.1)
print(*fit_evaluate_model(X_train, X_test, y_train, y_test, nn))
nn = MLPClassifier(hidden_layer_sizes=(5,), batch_size=128, learning_rate_init=0.01)
print(*fit_evaluate_model(X_train, X_test, y_train, y_test, nn))
nn = MLPClassifier(hidden_layer_sizes=(5,), batch_size=128, learning_rate_init=0.0001)
print(*fit_evaluate_model(X_train, X_test, y_train, y_test, nn))
nn = MLPClassifier(hidden_layer_sizes=(5,), batch_size=128, learning_rate_init=0.00001)
print(*fit_evaluate_model(X_train, X_test, y_train, y_test, nn))
We can see that an initial constant learning rate of 0.01 produces the best MLP accuracy so far. As a final experiment, we will make the learning rate adaptive with this initial value:
nn = MLPClassifier(hidden_layer_sizes=(5,), batch_size=128, learning_rate_init=0.01, learning_rate='adaptive')
print(*fit_evaluate_model(X_train, X_test, y_train, y_test, nn))
We can see that a hidden layer size of 5, a batch size of 128, and a constant initial learning rate of 0.001 produces the best accuracy of 99.1%.
Bayesians¶
For the Bayesian approach, we used a Naive Bayes classifier. By default, the NB classifier from scikit-learn has an alpha parameter of 1.0 that is a Lapace smoothing parameter, and it learns class prior proabilities by default. Below we can see the results of these default parameters:
# Bayesians
clf = MultinomialNB()
print(*fit_evaluate_model(X_train, X_test, y_train, y_test, clf))
Next we will play with the alpha parameter:
clf = MultinomialNB(alpha=0.8)
print(*fit_evaluate_model(X_train, X_test, y_train, y_test, clf))
clf = MultinomialNB(alpha=0.6)
print(*fit_evaluate_model(X_train, X_test, y_train, y_test, clf))
clf = MultinomialNB(alpha=0.4)
print(*fit_evaluate_model(X_train, X_test, y_train, y_test, clf))
clf = MultinomialNB(alpha=0.2)
print(*fit_evaluate_model(X_train, X_test, y_train, y_test, clf))
clf = MultinomialNB(alpha=0)
print(*fit_evaluate_model(X_train, X_test, y_train, y_test, clf))
Changing the smoothing parameter for this dataset seems to have only a slight effect on accuracy, but there is a larger drop in accuracy without smoothing. Finally, we test the Naive Bayes classifier with an alpha of 0.8 without learning class prior probabilities:
clf = MultinomialNB(alpha=0.8, fit_prior=False)
print(*fit_evaluate_model(X_train, X_test, y_train, y_test, clf))
We can see that a Naive Bayes classifier with an alpha parameter of 0.8 that does not learn prior class probabilities produces an accuracy of 98.6 percent, up from a Naive Bayes classifier that does learn prior class probabilities.
Analogizers¶
For the analogizers an SVM was considered over K-NN, as the sophistication of lazy learning much better served our purposes.
Interestingly, the linear kernel was both more computationally efficient and accurate than polynomial, radial basis and sigmoid kernels:
svm = SVC(kernel='linear')
print(*fit_evaluate_model(X_train, X_test, y_train, y_test, svm))
svm = SVC(kernel='rbf')
print(*fit_evaluate_model(X_train, X_test, y_train, y_test, svm))
svm = SVC(kernel='poly')
print(*fit_evaluate_model(X_train, X_test, y_train, y_test, svm))
svm = SVC(kernel='sigmoid')
print(*fit_evaluate_model(X_train, X_test, y_train, y_test, svm))
Evolutionaries¶
For this tribe of machine learning, we couldn't find an sklearn classifier that works directly on the dataset. The evolutionists' approach is all about evolving structures. Scikit has something that does just that for optimizing the performance of the other classifiers.
The Master Algorithm talks about Geoff Hinton and Steve Nowlan using genetic algorithms to evolve neural network structures and observing their fitness. This is what the book describes when they talk about combining nature (evolution) and nurture (learning).
Sklearn has something that does something similar to this combination of nature and nurture, and it so too much time to do it with our MLP because each generation has to wait for the results of backpropagation of several individuals in the genetic pool. We also tried sklearn's GA on the other models, and it had varying degrees of success.
It didn't work all that well when we asked the GA to tweak the parameters of the decision tree. In fact, the performance got worse:
#Evolutionaries
#Optimized Decision Tree with GA
dt_ga = get_model_geneticCV(dt)
print(*fit_evaluate_model(X_train, X_test, y_train, y_test, dt_ga))
plot_tree(dt_ga.estimator)
Here's the performance of the GA-tweaked MLP neural network on the validation set:
#Optimized MLP NN with GA
nn_ga = get_model_geneticCV(nn)
print(*fit_evaluate_model(X_train, X_test, y_train, y_test, nn_ga))
The worst-performing one of our classifiers was the one using k-nearest neighbors, with 64% accuracy on the test set. Here, sklearn's GA produces substantial improvement:
# KNN
neigh = KNeighborsClassifier(n_neighbors=3)
print(*fit_evaluate_model(X_train, X_test, y_train, y_test, neigh))
#Optimized KNN with GA
neigh_ga = get_model_geneticCV(neigh)
print(*fit_evaluate_model(X_train, X_test, y_train, y_test, neigh_ga))
Conclusion¶
We set out to explore the approaches of each one of the five tribes, using their techniques to build classifiers for detecting spam e-mail messages. Scikit-learn's built-in tools made this convenient, and it allows the results to be shown in one notebook. The routes taken by each one of the five tribes of machine learning are varied and interesting, and some worked better than others.
Domingos says that in the future, the master algorithm will eventually come from a combination of these five tribes. We already explored some of that here, making sklearn's genetic algorithm toolkit optimize the classifiers built on the other tribes' master algorithms. Possible future work could be for us to explore other combinations in more depth.
References¶
[1] Domingos, Pedro (2015). The Master Algorithm: How machine learning is reshaping how we live, Basic Books, ISBN 978-0465065707
[2] Apache SpamAssassin website, https://spamassassin.apache.org, accessed April 5, 2020
[3] Scikit-learn, https://scikit-learn.org/stable/index.html, accessed April 5, 2020
[4] Aurlien Gron. 2017. Hands-On Machine Learning with Scikit-Learn and TensorFlow: Concepts, Tools, and Techniques to Build Intelligent Systems (1st. ed.). O’Reilly Media, Inc.
Appendix¶
The remainder of our implementation, including the packages and helper functions that were used, are detailed below:
import os
import numpy as np
import pandas as pd
import email
import scipy
from sklearn.neighbors import KNeighborsClassifier
from sklearn.naive_bayes import MultinomialNB
from sklearn.model_selection import train_test_split
from sklearn.metrics import confusion_matrix
from sklearn import tree
from sklearn.svm import SVC
from sklearn.neural_network import MLPClassifier
from bs4 import BeautifulSoup as bs
import re
import s3fs
import nltk
import graphviz
import cv2
from nltk.stem import PorterStemmer
import matplotlib.pyplot as plt
import pydotplus
from sklearn.feature_extraction.text import TfidfVectorizer
from google.colab.patches import cv2_imshow
!pip install sklearn-genetic
from genetic_selection import GeneticSelectionCV
nltk.download('stopwords')
nltk.download('punkt')
# config for s3 bucket access
spam_buck = 's3://5tribes-spam'
ham_buck = 's3://5tribes-ham'
access_key = 'AKIAQIY225IKG72KFQ7L'
secret_key = '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'
fs = s3fs.S3FileSystem(key=access_key, secret=secret_key)
# oops i put one spam too many in the spam bucket...
print(len(fs.ls(spam_buck)), len(fs.ls(ham_buck)))
# load data from buckets into memory (pandas dataframe)
dir_contents = [fs.ls(spam_buck), fs.ls(ham_buck)]
dir_types = ["spam", "ham"]
dir_size = sum([len(ls) for ls in dir_contents])
arr = pd.DataFrame((dir_size, 2))
df_idx = 0
for i, dir_content in enumerate(dir_contents):
dir_type = dir_types[i]
for j, filepath in enumerate(dir_content):
# printing progress
if not (j+1) % 10: print(f"loaded {j+1}/{len(dir_content)} of {dir_type} bucket")
email_data = fs.cat(filepath)
message = email.message_from_bytes(email_data)
arr[df_idx] = (message, i)
df_idx += 1
dataset = arr.transpose()
def parse_email(email, strip_header=True, no_case=True, no_punc=True, \
no_stopwords=False, stemming=False, tokenize=False):
for sub_email in email.get_payload():
if type(sub_email) is not str:
return parse_email(sub_email, strip_header, no_case, no_punc, \
no_stopwords, stemming, tokenize)
if strip_header:
parsed_email = email.get_payload()
else:
parsed_email = email.as_string()
if no_case:
parsed_email = parsed_email.lower()
# removing markup relative to punctuation directive
if no_punc:
parsed_email, n = re.subn('[\n.!=",\']', ' ', bs(parsed_email).get_text())
else:
parsed_email = bs(parsed_email).get_text()
# tokenize the email, perform stemming and stopword removal
if tokenize:
tokenized_email = tokenizer(parsed_email)
if no_stopwords:
email_no_stop = []
for word in tokenized_email:
if not no_case: word = word.lower()
if word not in stopwords:
email_no_stop.append(word.lower())
tokenized_email = email_no_stop
if stemming:
stemmed_email = []
for word in tokenized_email:
if(word.isalpha()):
stemmed_email.append(ps.stem(word))
tokenized_email = stemmed_email
return " ".join(tokenized_email)
else:
return parsed_email
# required for parse_email func
stopwords = nltk.corpus.stopwords.words('english')
ps = PorterStemmer()
tokenizer = nltk.tokenize.word_tokenize
tfidf = TfidfVectorizer(tokenizer=tokenizer, stop_words=stopwords)
email_parser = np.vectorize(parse_email)
parsed = email_parser(dataset[0], stemming=True, no_punc=True, strip_header=True, no_stopwords=False, tokenize=True)
# get term frequency/inverse document frequencies of word unigrams and format labels
tfs_idfs = tfidf.fit_transform(parsed)
#labels = np.expand_dims(dataset[1], axis=1).astype(np.int)
labels = dataset[1].astype(np.int)
print(tfs_idfs.shape)
print(labels.shape)
# DATA SPLITTING
test_ratio = .2
state = 42
X_train, X_test, y_train, y_test = train_test_split(tfs_idfs, labels, test_size=test_ratio, random_state=state)
def fit_evaluate_model(X_train, X_test, y_train, y_test, model):
model.fit(X_train, y_train)
y_test_pred = model.predict(X_test)
acc = model.score(X_test, y_test)
cm = confusion_matrix(y_test, y_test_pred)
if type(model) == GeneticSelectionCV:
model_type = model.estimator_.__class__
else:
model_type = model.__class__
return model_type, '\n', acc, '\n', cm, '\n\n'
def get_model_geneticCV(model):
model_ga = selector = GeneticSelectionCV(model,
cv=5,
verbose=0,
scoring="accuracy",
max_features=5,
n_population=50,
crossover_proba=0.5,
mutation_proba=0.2,
n_generations=5,
crossover_independent_proba=0.5,
mutation_independent_proba=0.05,
tournament_size=3,
n_gen_no_change=10,
caching=True,
n_jobs=-1)
return model_ga
def plot_tree(model):
dot_data = tree.export_graphviz(model,
filled = True)
graph = pydotplus.graph_from_dot_data(dot_data)
graph.write_png('tree.png')
tree_png = cv2.imread('tree.png')
cv2_imshow(tree_png)
tfidf_voc_rev = dict([(v, k) for k, v in tfidf.vocabulary_.items()])
def print_word(idx):
print(idx, tfidf_voc_rev[idx])